package pers.qianyu.month_202101.date_20210108;

/**
 * 189. 旋转数组
 * https://leetcode-cn.com/problems/rotate-array/
 *
 * @author mizzle rain
 * @date 2021-01-08 17:39
 */
public class Rotate {
    // 模拟
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) return;
        k = k % len;
        if (k == 0) return;
        for (int cur = 0; cur < k; cur++) {
            int p1 = nums[len - 1];
            for (int i = len - 1; i >= 1; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = p1;
        }
    }

    // 反转
    public void rotate2(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) return;
        k = k % len;
        if (k == 0) return;
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    private void reverse(int[] arr, int left, int right) {
        while (left < right) {
            arr[left] = arr[left] + arr[right];
            arr[right] = arr[left] - arr[right];
            arr[left] = arr[left] - arr[right];
            left++;
            right--;
        }
    }

    // 辅助数组
    public void rotate3(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) return;
        k = k % len;
        if (k == 0) return;
        int[] result = new int[len];
        for (int i = 0; i < nums.length; i++) {
            result[(i + k) % len] = nums[i];
        }
        System.arraycopy(result, 0, nums, 0, len);
    }

    // 原地修改
    public void rotate4(int[] nums, int k) {
        int len = nums.length;
        if (len == 0) return;
        k = k % len;
        if (k == 0) return;
        int temp = nums[0];
        for (int i = 0; i < nums.length; i++) {
            temp = nums[(i + k) % len];
            nums[(i + k) % len] = nums[i];
        }
    }
}
